package com.congee02;

import java.util.Arrays;

public class SatisfiesConditions {

    public boolean satisfiesConditions(int[][] grid) {
        for (int[] e : cache) {
            Arrays.fill(e, -1);
        }
        return dfsHelp(grid, 0, 0, grid.length, grid[0].length);
    }

    private int[][] cache = new int[10][10];
    private boolean dfsHelp(int[][] grid, int x, int y, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return true;
        }
        if (cache[x][y] == -1) {
            boolean down = x + 1 >= m || grid[x][y] == grid[x + 1][y];
            boolean right = y + 1 >= n || grid[x][y] != grid[x][y + 1];
            boolean r = down && right && dfsHelp(grid, x + 1, y, m, n) && dfsHelp(grid, x, y + 1, m, n);
            cache[x][y] = r ? 1 : 0;
        }
        return cache[x][y] == 1;
    }

}
